#include"SList.h"

//打印
// void SLPrint (SLNode* phead)
// {
//     SLNode* pcur = phead;//保存一下第一个地址不动它
//     while (pcur)
//     {
//         printf("%d-->",pcur->data);
//         pcur=pcur->next;
//     }
//     printf("NULL\n");   
// }

//开一个新节点
SLNode* SLByNode(SLDataType x)
{
    SLNode* node=(SLNode*)malloc(sizeof(SLNode));
    node->data=x;
    node->next=NULL;
    return node;
}

//尾插
void SLPushBack (SLNode** pphead,SLDataType x)
{
    assert(pphead);
    SLNode* node=SLByNode(x);
    //判断头节点是否为空
    if(*pphead==NULL)
    {
        *pphead=node;
        return;
    }
    //不为空，先遍历链表，找到尾节点
    SLNode* pcur =*pphead;
    while(pcur->next!=NULL)
        pcur=pcur->next;
    pcur->next=node;
}
//头插
void SLPushFront (SLNode* *pphead,SLDataType x)
{
    assert(pphead);
    SLNode* node=SLByNode(x);
    node->next=*pphead;
    *pphead=node;
}
//尾删
void SLPopBack(SLNode** pphead)
{
    assert(pphead);
    //第一个节点也不能为空
    assert(*pphead);
    //只有一个节点,直接删掉头节点
    if((*pphead)->next==NULL)
    {
        free(*pphead);
        *pphead=NULL;
        return ;
    }
    //有多个节点，找尾节点和前一个节点
    SLNode* prev =NULL;
    SLNode* ptail =*pphead;
    while(ptail->next!=NULL)
    {
        prev=ptail;
        ptail=ptail->next;
    }
    prev->next=NULL;
    free(ptail);
    ptail=NULL;
}
//头删
void SLPopFront(SLNode** pphead)
{
    assert(pphead);
    //第一个节点也不能为空
    assert(*pphead);
    SLNode* pdel=*pphead;
    *pphead= (*pphead)->next;
    free(pdel);
    pdel=NULL;
}
//指定位置前插入
void SLInsert(SLNode* *pphead,SLNode*pos,SLDataType x)
{
    assert(pphead);
    //约定链表不能为空
    assert(pos);
    assert(*pphead);
    SLNode* node=SLByNode(x);
    //只有一个节点的情况(pos指向第一个节点)
    if((*pphead)->next==NULL || pos==*pphead)
    {
        node->next=*pphead;
        *pphead=node;
    }
    //有多个节点，找到pos的前一个节点
    SLNode* prev=*pphead;
    while(prev->next!=pos)
        prev=prev->next;
    prev->next=node;
    node->next=pos;
}
//指定位置后插入
void SLInsertAfter(SLNode*pos,SLDataType x)
{
    assert(pos);
    SLNode* node=SLByNode(x);
    node->next=pos->next;
    pos->next=node;
}
//找节点
// SLNode* SLFind(SLNode** pphead,SLDataType x)
// {
//     assert(pphead && *pphead);
//     SLNode* pcur=*pphead;
//     while(pcur)
//     {
//         if(pcur->data==x)
//             return pcur;
//         pcur=pcur->next;
//     }
//     return NULL;
// }
//删除pos节点
void SLErase(SLNode** pphead,SLNode* pos)
{
    assert(pphead && *pphead && pos);
    //只有一个节点的情况(或者pos指向第一个节点)
    if(pos==*pphead)
    {
        *pphead=(*pphead)->next;
        free(pos);
        pos=NULL;
        return ;
    }
    //有多个节点，找到pos的前一个节点
    SLNode* prev=*pphead;
    while(prev->next!=pos)
        prev=prev->next;
    prev->next=pos->next;
    free(pos);
    pos=NULL;
}
//删除pos之后的一个节点
void SLEraseAfter(SLNode* pos)
{
    assert(pos && pos->next);
    SLNode* del=pos->next;
    pos->next=del->next;
    free(del);
    del=NULL;
}
//链表的销毁
void SLDesTroy(SLNode** pphead)
{
    assert(pphead);
    SLNode* pcur=*pphead;
    while(pcur)
    {
        SLNode* next=pcur->next;
        free(pcur);
        pcur=next;
    }
    *pphead=NULL;
}

// //OJ题 删除链表中所有值为 val 的节点，并返回新的头节点
// //解法一：定义一个新链表，把不是val的节点挪过去
// SLNode* removeElements(SLNode* head, int val)
// {
//     SLNode* newhead=NULL;
//     SLNode* newtail=NULL;
//     SLNode* pcur=head;
//     while(pcur)
//     {
//         if(pcur->data!=val)
//         {
//             if(newhead==NULL)
//                 newhead=newtail=pcur;
//             else
//             {
//                 newtail->next=pcur;
//                 newtail=newtail->next;
//             }
//         }
//         pcur=pcur->next;
//     }
//     if(newtail)
//         newtail->next=NULL;
//     return newhead;
// }
// //解法二：在原链表中删
// SLNode* removeElements2(SLNode** head, int val)
// {
//     //判空
//     if(*head==NULL)
//         return NULL;
//     //找到第一个不为val的节点
//     while(*head)
//     {
//         if((*head)->data!=val)
//             break;
//         *head=(*head)->next;
//     }
//     SLNode* pcur=*head;
//     SLNode* pre=*head;
//     while(pcur)
//     {
//         if(pcur->data==val)
//         {
//             SLNode* pos=pcur;
//             pre->next=pcur->next;
//             pcur=pcur->next;
//             free(pos);
//             pos=NULL;
//         }
//         else
//         {
//             pre=pcur;
//             pcur=pcur->next;
//         }
//     }
//     return *head;
// }
// //OJ 反转链表
// SLNode* reverseList(SLNode* head)
// {
//     SLNode* p1=NULL;
//     SLNode* p2=head;
//     SLNode* p3=head;
//     while(p2)
//     {
//         p3=p3->next;
//         p2->next=p1;
//         p1=p2;
//         p2=p3;
//     }
//     return p1;
// }
// //OJ 合并两个有序链表
// SLNode* mergeTwoLists(SLNode* list1, SLNode* list2)
// {
//     if(list1==NULL)
//         return list2;
//     if(list2==NULL)
//         return list1;
//     //创建一个新链表
//     SLNode* newhead=NULL;
//     SLNode* newtail=NULL;
//     SLNode* p1=list1;
//     SLNode* p2=list2;
//     while(p1&&p2)
//     {
//         if(p1->data < p2->data)
//         {
//             if(newhead==NULL)//空链表
//                 newhead=newtail=p1;
//             else
//             {
//                 newtail->next=p1;
//                 newtail=newtail->next;
//             }
//             p1=p1->next;
//         }
//         else
//         {
//             if(newhead==NULL)
//                 newhead=newtail=p2;
//             else
//             {
//                 newtail->next=p2;
//                 newtail=newtail->next;
//             }
//             p2=p2->next;
//         }
//     }
//     if(p1)
//         newtail->next=p1;
//     if(p2)
//         newtail->next=p2;
//     return newhead;
// }
// //上面的代码冗余度很高，优化方法-->创建带头链表
// SLNode* mergeTwoLists2(SLNode* list1, SLNode* list2)
// {
//     if(list1==NULL)
//         return list2;
//     if(list2==NULL)
//         return list1;
//     //创建一个新链表(带头)
//     SLNode* newhead,*newtail;
//     newhead=newtail=(SLNode*)malloc(sizeof(SLNode));
//     SLNode* p1=list1;
//     SLNode* p2=list2;
//     while(p1&&p2)
//     {
//         if(p1->data < p2->data)
//         {
//             newtail->next=p1;
//             newtail=newtail->next;
//             p1=p1->next;
//         }
//         else
//         {
//             newtail->next=p2;
//             newtail=newtail->next;
//             p2=p2->next;
//         }
//     }
//     if(p1)
//         newtail->next=p1;
//     if(p2)
//         newtail->next=p2;
//     SLNode* ret=newhead->next;
//     free(newhead);
//     newhead=NULL;
//     return ret;
// }
// //OJ 找中间节点 快慢指针
// SLNode* middleNode(SLNode* head)
// {
//     if (head==NULL)
//         return NULL;
//     SLNode *fast,*slow;
//     fast=slow=head;
//     while(fast && fast->next)
//     {
//         //慢指针走一步，快指针走两步
//         slow=slow->next;
//         fast=fast->next->next;
//     }
//     return slow;
// }
// //OJ 环形链表的约瑟夫问题
// //创建一个循环不带头单链表
// SLNode* CreateList(int n)
// {
//     SLNode* head,*tail;
//     head=tail= SLByNode(1);
//     for(int i=2;i<=n;i++)
//     {
//         SLNode* node=SLByNode(i);
//         tail->next=node;
//         tail=tail->next;
//     }
//     //头尾相连
//     tail->next=head;
//     return tail;
//     //返回尾节点可以直接找到头节点，返回头节点需要遍历才能找到尾节点
// } 

// int ysf(int n,int m)
// {
//     //创建一个循环不带头单链表
//     SLNode* prev=CreateList(n);
//     SLNode* cur=prev->next;
//     int count =1;
//     while(cur!=cur->next)//判断是否只剩一个节点
//     {
//         if(count==m)
//         {
//             //删除节点
//             prev->next=cur->next;
//             free(cur);
//             cur=prev->next;
//             count=1;
//         }
//         else//接着往下数
//         {
//             prev=cur;
//             cur=cur->next;
//             count ++;
//         }
//     }
//     return cur->data;
// }
// //OJ 分隔链表
// SLNode* partition(SLNode* head, int x)
// {
//     if(head==NULL)
//         return NULL;
//     //创建两个新的带头链表
//     SLNode *greaterhead,*greatertail;
//     SLNode *lesshead,*lesstail;
//     SLNode* cur =head;
//     //创建哨兵位
//     lesshead=lesstail=(SLNode*) malloc(sizeof(SLNode));
//     greaterhead=greatertail=(SLNode*) malloc(sizeof(SLNode));
//     while(cur)
//     {
//         if(cur->data<x)//插入小链表中
//         {
//             lesstail->next=cur;
//             lesstail=lesstail->next;
//         }
//         else
//         {
//             greatertail->next=cur;
//             greatertail=greatertail->next;
//         }
//         cur=cur->next;
//     }
//     if(greaterhead)
//         greatertail->next=NULL;
//     //小链表尾接大链表头
//     lesstail->next=greaterhead->next;
//     SLNode* ret= lesshead->next;
//     free(greaterhead);
//     free(lesshead);
//     return ret;
// }